package leecode;

import lombok.val;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _448 {
    public static void main(String[] args) {
        int[] nums = new int[]{79,88,22,20,11,24,37,42,18,2,99,31,31,30,81,52,34,91,90,48,41,71,54,40,58,21,14,91,35,74,17,44,54,47,68,100,83,96,94,72,67,42,67,81,94,98,46,47,82,48,57,61,44,64,17,77,74,15,58,32,52,13,57,89,45,5,63,1,46,35,56,32,28,72,71,99,93,23,93,14,30,43,2,20,78,95,45,50,1,85,65,87,55,55,85,62,75,98,39,50};
        List<Integer> res = findDisappearedNumbers(nums);
        System.out.println(res);
    }

    public static List<Integer> findDisappearedNumbers(int[] nums) {
        int count = 0;
        int offset = 0;
        Arrays.sort(nums);
        for (int i = 1, j = 0; i <= nums.length; i++) {
            while (j < nums.length - 1 && nums[j] == nums[j + 1]) {
                j++;
            }
            if (j == 0 && i < nums[j]) {
                offset++;
            } else if (j >= nums.length || i != nums[j]) {
                nums[count++] = i;
            } else {
                j++;
            }
        }
        List<Integer> res = new ArrayList<>(count);
        for (int i = 0; i < count; i++) {
            res.add(nums[i]);
        }
        for (int i = 1; i <= offset; i++) {
            res.add(i);
        }
        return res;
    }
}
